//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;
class Solution {
public:
    //0-1背包问题，可以重复选择， 所以是一个完全背包问题
    //完全背包问题：
    //在wordDict 中可重复的选择字符事组合，看看是否存在可以组成字符事s的组合
    bool wordBreak(string s, vector<string>& wordDict) {
        //dp[i]：表示前i个字符组成的子串是否可以被 wordDict中的字符事组合而成
        vector<bool> dp(s.size()+1);
        dp[0] = true;

        //注意：这组的组合的顺序是在意的，所以先选择字符，再选择每个字符事
        for (int i = 1; i <= s.size(); ++i) { // 遍历背包
            for (string str:wordDict) { // 遍历物品
                int wordLen = str.length();
                if(i>=wordLen && s.substr(i-wordLen, wordLen)==str){
                    dp[i] = dp[i] || dp[i-wordLen];
                }
            }
        }
        return dp[s.size()];
    }
};